import java.util.Arrays;

/**
 * 股票最大利润
 */
public class Solution63 {

    public int maxProfit(int[] prices){
        if (prices == null || prices.length < 1)
            return 0;

        int[] dp = new int[prices.length];
        Arrays.fill(dp, 0);
        int min = prices[0];
        for (int i = 1; i < prices.length; i++){
            if (prices[i] > min)
                dp[i] = Math.max(dp[i - 1], prices[i] - min);
            else {
                min = prices[i];
                dp[i] = dp[i - 1];
            }
        }
        return dp[prices.length - 1];
    }
}
